package graph;

import java.util.Iterator;
import java.util.LinkedList;

import visitorpattern.Visitor;

import bookworm.Review;

public class BookReviewGraph implements BookReviewGraphInterface
{
	LinkedList<BookReviewEdge> bookReviewEdges;
	LinkedList<BookReviewNode> bookReviewNodes;
	public BookReviewGraph()
	{
		this.bookReviewEdges = new LinkedList<BookReviewEdge>();
		this.bookReviewNodes = new LinkedList<BookReviewNode>();
	}
	
	public int getNumberOfEdges()
	{
		return this.bookReviewEdges.size();
	}
	
	public int getNumberOfNodes()
	{
		return this.bookReviewNodes.size();
	}
	
	public boolean isDirected()
	{
		return false;//our BookReviewGraph is not directed.
	}
	
	/**
	 * creates a new BookReviewNode for the Graph
	 * @param reviewData is the data of a review associated with the new node
	 */
	public BookReviewNode createNewNode(Review reviewData)
	{
		BookReviewNode newNode = new BookReviewNode(reviewData);
		bookReviewNodes.add(newNode);
		
		return newNode;
	}
	
	
	public synchronized void createNewEdge(BookReviewNode nodeToConnect1,
															BookReviewNode nodeToConnect2)
	{
		BookReviewEdge newEdge = new BookReviewEdge(nodeToConnect1, nodeToConnect2);
		bookReviewEdges.add(newEdge);
	}
	
	public BookReviewEdge searchForEdge(BookReviewNode nodeConnected1, BookReviewNode nodeConnected2)
	{
		int indexOfEdgeInList = this.searchForEdgeIndex(nodeConnected1, nodeConnected2);
		if(indexOfEdgeInList != -1)
		{
			//edge was found in the list of the graph, then let's return it
			return this.bookReviewEdges.get(indexOfEdgeInList);
		}
		else
		{
			return null;//edge not found
		}
	}
	
	/**
	 * searches for the edge's index in the list bookReviewEdges from the Graph
	 * @param nodeConnected1 is one node connected by the edge 
	 * @param nodeConnected2 is another node connected by the edge
	 * @return the method returns the index
	 */
	private int searchForEdgeIndex(BookReviewNode nodeConnected1, BookReviewNode nodeConnected2)
	{
		for(int i = 0; i < this.bookReviewEdges.size(); i++)
		{
			BookReviewEdge edgeFromList = this.bookReviewEdges.get(i);
			if(edgeFromList.isConnectedToNode(nodeConnected1) &&
					edgeFromList.isConnectedToNode(nodeConnected2))
			{
				return i;
			}
		}
		
		return -1;//not found
	}
	
	public int searchForNodeIndex(BookReviewNode node)
	{
		if(node == null)
		{
			System.err.println("// asked to search null node");
		}
		for(int i = 0; i < this.bookReviewNodes.size(); i++)
		{
			BookReviewNode nodeinGraph = this.bookReviewNodes.get(i);
			if(node.getReviewData().getReviewId() == nodeinGraph.getReviewData().getReviewId())
			{
				return i;
			}
		}
		
		return -1;//node not found
	}
	
	
	public BookReviewNode searchForNode(Review reviewOfNode)
	{
		int indexOfNodeInList = this.searchForNodeIndex(reviewOfNode);
		if(indexOfNodeInList != -1)
		{
			//node was found in list of graph
			return this.bookReviewNodes.get(indexOfNodeInList);
		}
		else
		{
			return null;//not found
		}
	}
	
	/**
	 * 
	 * @param reviewOfNode
	 * @return  returns the index of the node inside graph's node storage 
	 */
	private int searchForNodeIndex(Review reviewOfNode)
	{
		for(int i = 0; i < this.bookReviewNodes.size(); i++)
		{
			BookReviewNode bookReviewNode = this.bookReviewNodes.get(i);
			Review reviewFromNode = bookReviewNode.getReviewData();
			if(reviewFromNode.getReviewId() == reviewOfNode.getReviewId())
			{
				return i;
			}
		}
		return -1;//not found
	}
	
	public void removeNode(Review reviewDataToRemove)
	{
		int indexBookReviewToRemove = this.searchForNodeIndex(reviewDataToRemove);
		if(indexBookReviewToRemove != -1)
		{
			//node was found, let's remove it
			BookReviewNode nodeRemoved = this.bookReviewNodes.remove(indexBookReviewToRemove);
			//we must also remove the edges connected to the node
			LinkedList<BookReviewEdge> incidentEdgesFromNodeRemoved = nodeRemoved.getIncidentEdges();
			for(int i = 0; i < incidentEdgesFromNodeRemoved.size(); i++)
			{
				BookReviewEdge edgeToRemove = incidentEdgesFromNodeRemoved.get(i);
				this.bookReviewEdges.remove(edgeToRemove);
				//we must also remove it's references in the nodes which were connected by it
				edgeToRemove.getFirstNodeConnected().removeIncidentEdge(edgeToRemove);
				edgeToRemove.getSecondNodeConnected().removeIncidentEdge(edgeToRemove);
			}
		}
	}
	
	public synchronized void removeEdge(BookReviewNode nodeConnected1,
															BookReviewNode nodeConnected2)
	{
		int indexEdgeToRemoveInGraphList = this.searchForEdgeIndex(nodeConnected1, nodeConnected2);
		if(indexEdgeToRemoveInGraphList != -1)
		{
			//edge was found in the search. Let's remove it
			BookReviewEdge edgeToRemove = this.bookReviewEdges.remove(indexEdgeToRemoveInGraphList);
			//we must also remove it's references in the nodes which were connected by it
			edgeToRemove.getFirstNodeConnected().removeIncidentEdge(edgeToRemove);
			edgeToRemove.getSecondNodeConnected().removeIncidentEdge(edgeToRemove);
		}
	}
	
	/**
	 * given 2 reviews, we'll search on the graph for this reviews and then see if there's
	 * and edge between these two nodes
	 */
	public boolean isThereAnEdgeBetweenReviews(Review reviewData1, Review reviewData2)
	{
		BookReviewNode nodeOfReviewData1 = this.searchForNode(reviewData1);
		if(nodeOfReviewData1 != null)
		{
			BookReviewNode nodeOfReviewData2 = this.searchForNode(reviewData2);
			if(nodeOfReviewData2 != null)
			{
				if(nodeOfReviewData1.isAlreadyConnectedTo(nodeOfReviewData2) == true)
				{
					//nodes are already connected
					return true;
				}
				else
				{
					//nodes are not connected
					return false;
				}
			}
			else
			{
				//node Of Review Data2 not found
				return false;
			}
		}
		else
		{
			//node Of Review Data1 not found
			return false;
		}
	}
	
	public Iterator<BookReviewEdge> getBookReviewEdges()
	{
		return this.bookReviewEdges.iterator();
	}
	
	public Iterator<BookReviewNode> getBookReviewNodes()
	{
		return this.bookReviewNodes.iterator();
	}
	
	public LinkedList<BookReviewNode> depthFirstTraversal(Visitor visitsNode)
	{
		int numberOfNodes = this.bookReviewNodes.size();
		boolean[] nodesWereVisited = new boolean[numberOfNodes];
		for(int i = 0; i < numberOfNodes; i++)
		{
			nodesWereVisited[i] = false;
		}
		
		/*our graph can have many subgraphs which are not connected. Luckily, we've
		 * already prepared starting nodes for our graph with the class 
		 * AdministratorOfAllStatingNodes(which is a singleton, just for you to know).
		 * It can return to us the starting nodes so that we can be sure that the whole graph was 
		 * visited.*/
		LinkedList<BookReviewNode> nodesVisited = new LinkedList<BookReviewNode>();
		
		LinkedList<BookReviewNode> startingNodes = 
				AdministratorOfAllStartingNodes.getAdministratorOfAllStartingNodes().getAllStartingNodesFromAllTags();
		
		for(int j = 0; j < startingNodes.size(); j++)
		{
			//for every starting node, we'll start a depthFirstTraversal from it.
			BookReviewNode startingNode = startingNodes.get(j);
			
			this.depthFirstTraversal(visitsNode, startingNode, nodesWereVisited, nodesVisited);
		}
		
		
		
		return nodesVisited;
	}
	
	private void depthFirstTraversal(Visitor visitsNode, BookReviewNode node,
							boolean [] nodesWereVisited, LinkedList<BookReviewNode> nodesVisited)
	{
	
		if(node != null)//if node is null, then we have nothing to visit, right?
		{
			//we'll have to look for node's index
			int indexOfNode = this.searchForNodeIndex(node);
			if(indexOfNode != -1)//node was found in graph
			{
				if(nodesWereVisited[indexOfNode] != true)
				{
					/*why do we check if this node is already visited? because in our graph there can be
					 * one node that is the starting node for two tags consecutively. Obviously, the traversal
					 * will visit him 2 times without even checking if it's already visited.
					 * This doesn't make the algorithm's complexity go higher. 
					 */
					node.accept(visitsNode);
					nodesWereVisited[indexOfNode] = true;//node visited
					//we'll also add this visited node in the list passed as parameter from method
					nodesVisited.add(node);
				}
				
				LinkedList<BookReviewNode> neighborsOfNode = node.getNeighborsOfNode();
				for(int j = 0; j < neighborsOfNode.size(); j++)
				{
					BookReviewNode neighborOfNode = neighborsOfNode.get(j);
					int indexOfNeighborOfNode = this.searchForNodeIndex(neighborOfNode);
					
					if(nodesWereVisited[indexOfNeighborOfNode] != true)
					{
						depthFirstTraversal(visitsNode, neighborOfNode, nodesWereVisited,
																					nodesVisited);
					}
				}
			}
			
		}
	}
	
	
	
	
	
	
	public LinkedList<BookReviewNode> breadthFirstTraversal(Visitor visitsNode)
	{	
		LinkedList<BookReviewNode> nodesVisited = new LinkedList<BookReviewNode>();
		LinkedList<BookReviewNode> startingNodes = 
				AdministratorOfAllStartingNodes.getAdministratorOfAllStartingNodes().getAllStartingNodesFromAllTags();
		int numberOfNodes = this.bookReviewNodes.size();
		boolean[] nodesWereEnqueued = new boolean[numberOfNodes];/*this array was supposed to be created
																	inside the private breadthFirstTraversal, but since we're
																	going to call the method many times(with other starting nodes), it's safer
																	to create it here so that we can use it equally in all method calls.*/
		for(int i = 0; i < numberOfNodes; i++)
		{
			nodesWereEnqueued[i] = false;
			//initially, none of the nodes were enqueued for visit in the traversal...
		}
		
		for(int j = 0; j < startingNodes.size(); j++)
		{
			/*
			 * we might want to check if there isn't a duplicate starting node based on tags
			 * because in our graph it's possible(for example: let's say a book
			 * review is the starting node for the tag "horror" and "vampire". Then there would be
			 * two starting nodes which are the same thing. Let's check if a node was already 
			 * a starting node in a previous traversal to avoid running through the same traversal)
			 */
			
			BookReviewNode startingNode = startingNodes.get(j);
			boolean wasAlreadyAStartingNode = false;
			for(int i = j - 1; i >= 0; i--)
			{
				/*we'll check in the precedent starting nodes if there isn't a node
				equal to the one we're about to traverse*/
				BookReviewNode initialNodeAlreadyTraversed = startingNodes.get(i);
				if(initialNodeAlreadyTraversed == startingNode)
				{
					wasAlreadyAStartingNode = true;
				}
			}
			
			if(wasAlreadyAStartingNode == false)
			{
				this.breadthFirstTraversal(visitsNode, startingNode,
															nodesVisited, nodesWereEnqueued);
			}
		}
		
		return nodesVisited;
	}
	
	private void breadthFirstTraversal(Visitor visitsNode, BookReviewNode startingNode,
							LinkedList<BookReviewNode> nodesVisited, boolean [] nodesWereEnqueued )
	{
		if(startingNode != null)
		{
			
			
			LinkedList<BookReviewNode> queueOfNodes = new LinkedList<BookReviewNode>();
			//we'll treat the linkedList above as a queue
			
			//first let's enqueue the starting node
			int startingNodeIndex = this.searchForNodeIndex(startingNode);
			if(nodesWereEnqueued[startingNodeIndex] != true)
			{
				/*if the node was previously queued, then it has already been visited(and
				 * all of it's neighbors). We don't want to visit them again, do we?
				 * In our graph, it is quite possible for this conditional to occur
				 * because our starting nodes are the starting nodes related to book tags. Then we could
				 * already have visited a starting node previously in a previous traversal.
				 */
				nodesWereEnqueued[startingNodeIndex] = true;
				queueOfNodes.addLast(startingNode);
				
				//now the function only ends when this queueOfNodes is empty.
				while(queueOfNodes.isEmpty() == false)
				{
					BookReviewNode dequeuedNode = queueOfNodes.removeFirst();
					
					dequeuedNode.accept(visitsNode);
					nodesVisited.add(dequeuedNode);
					
					LinkedList<BookReviewNode> neighborsOfDequeuedNode = 
												dequeuedNode.getNeighborsOfNode();
					for(int j = 0; j < neighborsOfDequeuedNode.size(); j++)
					{
						BookReviewNode neighborOfDequeuedNode = neighborsOfDequeuedNode.get(j);
						int indexOfNeighbor = this.searchForNodeIndex(neighborOfDequeuedNode);
						if(nodesWereEnqueued[indexOfNeighbor] == false)
						{
							nodesWereEnqueued[indexOfNeighbor] = true;
							queueOfNodes.addLast(neighborOfDequeuedNode);
						}
					}
				}
			}
		}
	}
}
